package main

// 25. K 个一组翻转链表 https://leetcode.cn/problems/reverse-nodes-in-k-group
func reverseKGroupV2(head *ListNode, k int) *ListNode {
	if head == nil {
		return nil
	}
	end := head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}

	curr := head
	var prev *ListNode
	var next *ListNode
	for curr != end {
		next = curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}

	head.Next = reverseKGroup(end, k)
	return prev
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil {
		return nil
	}
	end := head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}

	newHead := reverseRange(head, end)
	head.Next = reverseKGroup(end, k)
	return newHead
}
func reverseRange(head, end *ListNode) *ListNode {
	curr := head
	var prev *ListNode
	var next *ListNode
	for curr != end {
		next = curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

// 86. 分隔链表 https://leetcode.cn/problems/partition-list/
// 另启一个 bigger 节点，遇到大的，就往后面加
func partition(head *ListNode, x int) *ListNode {
	dummyA := &ListNode{Next: head}
	dummyB := &ListNode{}
	pA := dummyA
	pB := dummyB

	for pA.Next != nil {
		if pA.Next.Val < x {
			pA = pA.Next
			continue
		}
		pB.Next = pA.Next      //节点入新 list
		pA.Next = pA.Next.Next //原 list 删除节点 不用后移

		// 新 list 指针后移，且清空后面指针
		pB = pB.Next
		pB.Next = nil
	}
	pA.Next = dummyB.Next
	return dummyA.Next
}

// 61. 旋转链表
// https://leetcode.cn/problems/rotate-list
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 一趟遍历判断有多少元素
	n := 0
	p := head
	for p != nil {
		p = p.Next
		n++
	}
	// 确定要旋转多少步
	k = k % n
	if k == 0 {
		return head
	}

	// 快指针先走一步
	q := head
	for i := 0; i < k; i++ {
		q = q.Next
	}

	// 在旋转后的最后一个节点停下
	p = head
	for q.Next != nil {
		q = q.Next
		p = p.Next
	}
	newHead := p.Next
	q.Next = head
	p.Next = nil
	return newHead
}

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

// 138. 随机链表的复制
func copyRandomList(head *Node) *Node {
	cache := map[*Node]*Node{}
	p := head
	for p != nil {
		cache[p] = &Node{Val: p.Val}
		p = p.Next
	}

	newHead := &Node{}
	prev := newHead
	p = head
	for p != nil {
		newNode := cache[p]
		prev.Next = newNode
		newNode.Next = cache[p.Next]
		newNode.Random = cache[p.Random]
		p = p.Next
		prev = prev.Next
	}
	return newHead.Next
}

// 82. 删除排序链表中的重复元素 II https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	prev := dummy

	for prev.Next != nil && prev.Next.Next != nil {
		p1 := prev.Next.Next
		p2 := prev.Next
		if p1.Val != p2.Val {
			prev = prev.Next
			continue
		}

		for p1 != nil && p1.Val == p2.Val {
			p1 = p1.Next
			p2 = p2.Next
		}
		prev.Next = p1
	}
	return dummy.Next
}

// 19 删除倒数第 N 个节点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
// 难点在于要有个 dummy 指针
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	p1 := head
	for i := 0; i < n; i++ {
		p1 = p1.Next
	}

	p2 := dummy
	for p1 != nil {
		p1 = p1.Next
		p2 = p2.Next
	}
	p2.Next = p2.Next.Next
	return dummy.Next
}

// 反转链表2 https://leetcode.cn/problems/reverse-linked-list-ii/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == 1 {
		return reverseN(head, right)
	}
	head.Next = reverseBetween(head.Next, left-1, right-1)
	return head
}

var successor *ListNode

func reverseN(head *ListNode, n int) *ListNode {
	if n == 1 {
		successor = head.Next
		return head
	}
	newHead := reverseN(head.Next, n-1)
	head.Next.Next = head
	head.Next = successor
	return newHead
}

// 21 反转链表 https://leetcode.cn/problems/reverse-linked-list/
// 循环方式实现
// 需要一直持有后面的节点，然后断开当前节点，指向原来节点
func reverseList(head *ListNode) *ListNode {
	var (
		prev *ListNode
		curr *ListNode
		next *ListNode
	)
	curr = head
	for curr != nil {
		next = curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

// 递归方式
// 这个函数的作用就是 返回一个新的头指针
// 只需要确定递归出口
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	tmp := head.Next
	newHead := reverseList2(head.Next)
	tmp.Next = head
	head.Next = nil
	return newHead
}
